package com.example.demo.algorithm.lesson.basic.class1;

/**
 * @author liweizhi
 * @date 2020/4/22 19:27
 */
public class EvenAndOddTimeNumber {
    static void findTheOneEvenNumber(int[] arr) {
        int a = 0;
        for (int i : arr) {
            a ^= i;
        }
        System.out.println("find:" + a);
    }

    static void findTheTwoEvenNumber(int[] arr) {
        int a = 0;
        for (int i : arr) {
            a ^= i;
        }
        // now a = x1 ^ x2
        // 找到a最右面的"1"
        int j = a & ((~a) + 1);
        int x1 = 0;
        int x2;
        for (int i : arr) {
            if ((i & j) == 0) {
                // 和所有j位不是1的数做异或
                x1 ^= i;
            }
        }
        // now x1 is one of the two,and a = x1 ^ x2,so
        x2 = a ^ x1;

        System.out.println("002 find:" + x1);
        System.out.println("002 find:" + x2);
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 3, 4, 5, 5};
        findTheOneEvenNumber(arr);
        int[] arr2 = {111, 1, 1, 2, 2, 3, 3, 4, 5, 5};
        findTheTwoEvenNumber(arr2);
    }
}
